1. 题目

Dota2 的世界里有两个阵营：Radiant(天辉)和 Dire(夜魇)

Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的一项：

禁止一名参议员的权利：

参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利。

宣布胜利：

如果参议员发现有权利投票的参议员都是同一个阵营的，他可以宣布胜利并决定在游戏中的有关变化。

给定一个字符串代表每个参议员的阵营。字母 “R” 和 “D” 分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。

以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。

假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 Radiant 或 Dire。

示例 1：输入："RD" 输出："Radiant" 解释：第一个参议员来自 Radiant 阵营并且他可以使用第一项权利让第二个参议员失去权力，因此第二个参议员将被跳过因为他没有任何权利。然后在第二轮的时候，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人

示例 2：输入："RDD" 输出："Dire" 解释：第一轮中,第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利第二个来自 Dire 阵营的参议员会被跳过因为他的权利被禁止第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利

提示：给定字符串的长度在 [1, 10,000] 之间.

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/dota2-senate 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

读懂题意之后，关键的问题就是禁止他人的权利这项权利该对谁用。

可以发现，这项权利应该对后面的对方阵营的第一个人用（当然，如果后方没有对面阵营的人的话，应该对前面的对方阵营的人用）。

以"RDDR"为例：

第一个R为了对自己的政党做出最好的策略，肯定会禁止掉第一个对方阵营D的权利；
这样，第一个D的权利就被禁止了，不能参加下一轮；
第二个D这时候有两个选择，要么禁止第一个R参加下一轮的权利，要么禁止掉第二个R参加下一轮的权利。这时候，很显然，第一个D已经用掉了禁止他人的权利，而第二个D还没用，为了对自己的政党做出最好的策略，所以肯定选择后者——禁止掉二个R参加下一轮的权利。
这样，第二个R的权利就被禁止了，不能参加下一轮；
下一轮开始，第一轮中的第一个R和第一个D进入第二轮，变成了“RD”
R禁止掉D的权利。R进入第三轮。最后R方阵营胜利。

接下来是如何实现：

2.1. 暴力

按照上面的最优策略，可以用一个队列表示每轮的参议员，再求出每次进入下一轮的参议员。再判断这一轮是否只有一个阵营的人。

2.2. 优化

可以用两个队列分别存储两方参议员的位置，根据相对位置判断，若是可以禁止他人的权利，则将被禁止的人pop掉，行使权利的人将位置+n（总人数)后再加入队列即可。直至一方队列为空。

3. 代码

3.1. 暴力

class Solution {
public:
    queue<char> nextRound(queue<char>& Q){//求出每次进入下一轮的参议员
        int curR=0,curD=0;//目前有权的
        queue<char> que;

        while(!Q.empty()){
            char x = Q.front();Q.pop();
            if(x=='R'){
                if(curD) curD--;//前面如果有对面阵营的人，这时候会被禁止掉权利
                else {
                    que.push('R');//暂时加入下一轮
                    if(Q.empty() && que.front()=='D') que.pop();
                    else curR++;
                }
            }else {//同上
                if(curR) curR--;
                else {
                    que.push('D');
                    if(Q.empty() && que.front()=='R') que.pop();
                    else curD++;
                }
            }
        }
        Q = que;
        while(!que.empty()){
            que.pop();
        }
        while(!Q.empty()){//如果有人的权利还没用掉，可以对前面出现的对方阵营的人使用
            if(Q.front() == 'R'){
                if(curD) curD--;
                else que.push('R');
            }else{
                if(curR) curR--;
                else que.push('D');
            }Q.pop();
        }
        return que;
    }
    char predict(queue<char> Q){
        queue<char> que = nextRound(Q);
        Q = que;
        bool flag = true;
        char x = Q.front();Q.pop();
        while(!Q.empty()){
            if(Q.front() != x) {
                flag = false;break;
            }Q.pop();
        }
        if(flag) return x;
        else return predict(que);
    }
    string predictPartyVictory(string senate) {
        int n = senate.size();
        queue<char> Q;
        for(auto &x:senate){
            Q.push(x);
        }

        if(predict(Q) == 'R') return "Radiant";
        else return "Dire";

    }
};

这次实现太过臃肿了唉

3.2. 优化

class Solution {
public:
    string predictPartyVictory(string senate) {
        int n = senate.size();
        queue<int> Radiant,Dire;
        for(int i=0;i<n;++i){
            if(senate[i] == 'R') Radiant.push(i);
            else Dire.push(i);
        }

        while(!Radiant.empty() && !Dire.empty()){
            int r = Radiant.front();
            int d = Dire.front();

            if(r<d) Radiant.push(r+n);
            else if(r>d) Dire.push(d+n);

            Radiant.pop();
            Dire.pop();
        }

        return Radiant.empty()?"Dire":"Radiant";
    }
};

649 Dota2 参议院